In recent years, multiple input multiple output (MIMO) technique has been studied as a next-generation communication technique. In the MIMO system, a transmitter which is provided with a plurality of transmission antennas (for example, M antennas) transmits a plurality of data streams and a receiver which is provided with a plurality of reception antennas (for example, N antennas) receives the plurality of data streams in a separate manner. Here, M≦N holds.
For the sake of expediency in description, a case where a transmitter transmits M data streams which are equal to the number of transmission antennas is described as an example, here. A receiver receives N reception signals. Here, when a data stream is denoted as a vector x in the M-th row and the first column, a channel matrix in the N-th row and M-th column which has a propagation path gain hij between the j-th transmission antenna and the i-th reception antenna as an element is denoted as H, a reception signal is denoted as a vector y in the N-th row and first column, and a noise is denoted as a vector n in the N-th row and first column, expression (1) is obtained.
                    y        =                              Hx            +                          n              ⁢                                                          (                                                                                          y                      1                                                                                                                                  y                      2                                                                                                            ⋮                                                                                                              y                      N                                                                                  )                                =                                                    (                                                                                                    h                        11                                                                                                            h                        12                                                                                    ⋯                                                                                      h                                                  1                          ,                          M                                                                                                                                                                        h                        21                                                                                                            h                        22                                                                                    ⋯                                                                                      h                                                  2                          ,                          M                                                                                                                                                ⋮                                                              ⋮                                                              ⋱                                                              ⋮                                                                                                                          h                                                  N                          ,                          1                                                                                                                                    h                                                  N                          ,                          2                                                                                                            ⋯                                                                                      h                                                  N                          ,                          M                                                                                                                    )                            ⁢                              (                                                                                                    x                        1                                                                                                                                                x                        2                                                                                                                        ⋮                                                                                                                          x                        M                                                                                            )                                      +                          (                                                                                          n                      1                                                                                                                                  n                      2                                                                                                            ⋮                                                                                                              n                      N                                                                                  )                                                          (        1        )            
Examples of a stream separation method on the reception side include minimum mean square error (MMSE) and maximum likelihood detection (MLD). In MLD, metrics such as a squared Euclidean distance are calculated with respect to all symbol replica candidate combinations of a plurality of stream signals so as to set a combination, which has the minimum sum metric, as a signal after stream separation. In MLD, a superior reception performance is obtained compared to a linear separation method such as MMSE. However, when a modulation multi-level number of the l-th transmission signal is denoted as ml (for example, m=4 in a case of QPSK, m=16 in a case of 16QAM, and m=64 in a case of 64QAM), a combination number is expressed as expression (2).
                              ∏                      k            =            1                    M                ⁢                  m          k                                    (        2        )            
As expressed in expression (2), as a modulation multi-level number and the number of transmission streams are increased, the number of times of metric calculation is increased in an exponential fashion, causing an enormous amount of processing disadvantageously. Therefore, various types of arithmetic amount reduction type MLD have been proposed.
In related art, QRM-MLD in which QR decomposition and M algorithm are combined with each other has been proposed. In QRM-MLD, metrics such as a squared Euclidean distance from all symbol replica candidates are calculated with respect to surviving symbol replica candidates on the previous stage. When k=1, . . . , and the number of surviving candidates on the M-th stage is denoted as Sk, the number of times of metric calculation becomes as expression (3).
                              S          1                +                              ∑                          k              =              2                        M                    ⁢                                    m              k                        ⁢                          S                              k                -                1                                                                        (        3        )            
In related art, a method of adaptive selection of surviving symbol replica candidates based on the maximum reliability (ASESS) in which a method for reducing the number of times of metric calculation is further applied to QRM-MLD has been proposed. Symbol replica candidates on respective stages are ranked through region detection and metric calculation is performed as many times as the number of surviving symbol replica candidates, with respect to symbol replicas in an ascending order of cumulative values of metrics. When k=1, . . . , and the number of surviving candidates on the M-th stage is denoted as Sk, the number of times of metric calculation is expressed as expression (4).
                              ∑                      k            =            1                    M                ⁢                  S          k                                    (        4        )            
In ASESS method, the number of times of metric calculation is linearly increased with respect to the number of transmission streams. Further, Japanese Laid-open Patent Publication No. 2006-270430 has disclosed a method in which ranking of symbol candidates is applied to the list sphere decoding (LSD) method.
The ASESS method is described in detail. In order to simplify the description, a case of M=N is taken as an example. In the ASESS method, a channel matrix H is QR-decomposed into a unitary matrix Q and an upper triangular matrix R as expression (5).
                    H        =                  QR          =                                    (                                                                                          q                      11                                                                                                  q                      12                                                                            ⋯                                                                              q                                              1                        ,                        N                                                                                                                                                        q                      21                                                                                                  q                      22                                                                            ⋯                                                                              q                                              2                        ,                        N                                                                                                                                  ⋮                                                        ⋮                                                        ⋱                                                        ⋮                                                                                                              q                                              N                        ,                        1                                                                                                                        q                                              N                        ,                        2                                                                                                  ⋯                                                                              q                                              N                        ,                        N                                                                                                        )                        ⁢                          (                                                                                          r                      11                                                                                                  r                      12                                                                            ⋯                                                                              r                                              1                        ,                        N                                                                                                                                                                                                                                                          r                      22                                                                            ⋯                                                                              r                                              2                        ,                        N                                                                                                                                                                                                                                                                                                                                      ⋱                                                        ⋮                                                                                                                                                                                          O                                                                                                                                                                                r                                              N                        ,                        N                                                                                                        )                                                          (        5        )            
O denotes a zero matrix. In the ASESS method, multiplication of a reception signal y by Hermitian conjugates of the unitary matrix Q from the left enables orthogonalization as expression (6).
                                                        z              =                            ⁢                                                Q                  H                                ⁢                y                                                                                        =                            ⁢                                                                    Q                    H                                    ⁢                  QRx                                +                                                      Q                    H                                    ⁢                  n                                                                                                        =                            ⁢                              Rx                +                                                      n                    ′                                    ⁡                                      (                                                                                                                        z                            1                                                                                                                                                                            z                            2                                                                                                                                                ⋮                                                                                                                                                  z                            N                                                                                                                )                                                                                                                          =                            ⁢                                                                    (                                                                                                                        r                            11                                                                                                                                r                            12                                                                                                    ⋯                                                                                                      r                                                          1                              ,                              N                                                                                                                                                                                                                                                                                                                                        r                            22                                                                                                    ⋯                                                                                                      r                                                          2                              ,                              N                                                                                                                                                                                                                                                                                                                                                                                                                                            ⋱                                                                          ⋮                                                                                                                                                                                                                                                      O                                                                                                                                                                                                                                      r                                                          N                              ,                              N                                                                                                                                            )                                    ⁢                                      (                                                                                                                        x                            1                                                                                                                                                                            x                            2                                                                                                                                                ⋮                                                                                                                                                  x                            N                                                                                                                )                                                  +                                  (                                                                                                              n                          1                          ′                                                                                                                                                              n                          2                          ′                                                                                                                                    ⋮                                                                                                                                      n                          N                          ′                                                                                                      )                                                                                        (        6        )            
In the ASESS method, region detection on the lowest stage is performed by expression (7) so as to determine a region number ε(1) of a region to which uN belongs, on the first stage.uN=zN/rN,N  (7)
In the ASESS method, region detection includes the Ndiv times of quadrant detection and the Ndiv−1 times of origin movement, and a region to which uN belongs among 22Ndiv regions is detected. In the ASESS method, a symbol ranking table Ω is referred to and as many candidate replicas as S1, the number of surviving candidates from the higher ranking, are set as surviving paths of the first stage so as to calculate a metric such as a squared Euclidean distance. When a surviving path is expressed as expression (8) and a metric is a squared Euclidean distance, the metric is expressed as expression (9).Π1(1)(i)=Ω(mN)(ε,i)  (8)d1(Π1(1)(i))=|zN−rN,NcN,Π1(1)(i)|2, i=1, 2, . . . , S1  (9)
Here, Ω(4), Ω(16), and Ω(64) respectively represent symbol ranking tables with respect to QPSK, 16QAM, and 64QAM. Expression (10) expresses the symbol number of the i-th order in ranking with respect to a region number ε(1) which is stored in the symbol ranking table.Ω(mN)(ε(1),i)  (10)
In the ASESS method, region detection by expression (11) in which candidate replicas of S1 surviving paths, which are survived on the first stage, are respectively cancelled from a reception signal zN−1 which is the second lowest signal is performed so as to determine a region number ε(1)(i) of a region to which u expressed as expression (12) belongs, on the second stage.uN−1(Π1(1)(i))=(zN−1−rN−1,NcN,Π1(1)(i))/rN−1,N−1, i=1, 2, . . . , S1  (11)uN−1(Π1(1)(i))  (12)
In the ASESS method, a surviving path on the second stage is adaptively selected as following. In the ASESS method, a representative cumulative metric value E(i) and a current rank ρ(i) of each surviving path which is survived on the first stage are first initialized so as to obtain expression (13), expression (14), and expression (15).E(i):=d1(Π1(1)(i))  (13)ρ(i):=1  (14)q:=1  (15)
In the ASESS method, a candidate replica on the ρ(imin)-th order in the ranking of imin at which ρ(i)≦mN is satisfied and E(i) has the minimum value is selected from the symbol ranking table and the q-th surviving path on the second stage is expressed as expression (16) and expression (17).
                                                        ∏              1                              (                2                )                                      ⁢                          (              q              )                                =                                    ∏              1                              (                1                )                                      ⁢                          (                              i                                  m                  ⁢                                                                          ⁢                  i                  ⁢                                                                          ⁢                  n                                            )                                      ⁢                                  ⁢                                            ∏              2                              (                2                )                                      ⁢                          (              q              )                                =                                    Ω                              (                                  m                                      N                    -                    1                                                  )                                      ⁡                          (                                                                    ɛ                                          (                      2                      )                                                        ⁡                                      (                                          i                                              m                        ⁢                                                                                                  ⁢                        i                        ⁢                                                                                                  ⁢                        n                                                              )                                                  ,                                  ρ                  ⁡                                      (                                          i                                              m                        ⁢                                                                                                  ⁢                        i                        ⁢                                                                                                  ⁢                        n                                                              )                                                              )                                                          (        16        )                                          i                      m            ⁢                                                  ⁢            i            ⁢                                                  ⁢            n                          =                              arg                                          ρ                ⁡                                  (                  i                  )                                            ≤                              m                                  N                  -                  1                                                              ⁡                      (                          min              ⁡                              [                                  e                  ⁡                                      (                    i                    )                                                  ]                                      )                                              (        17        )            
A cumulative metric is calculated as expression (18).d2(Π(2)(q))=d1(Π1(1)(imin))+|zN−1−rN−1,NcN,Π1(1)(imin)−rN−1,N−1cN−1,Π2(2)(q)|2  (18)
Then, in the ASESS method, the cumulative metric is updated as expression (19), expression (20), and expression (21).E(imin):=d2(Π(2)(q))  (19)ρ(imin):=ρ(imin)+1  (20)q:=q+1  (21)
In the ASESS method, the above-mentioned processing is performed until q reaches the number S2 of surviving paths of the second stage. In the ASESS method, region detection by expression (22) in which candidate replicas of Sk−1 surviving paths, which are survived on the k−1-th stage, are respectively cancelled from a reception signal zN−k+1 which is the k-th lowest signal is performed so as to determine a region number ε(k) of a region to which u expressed as expression (23) belongs, on the following k-th stage.
                                                        u                                                N                  -                  k                  +                  1                                ,                i                                      ⁡                          (                                                Π                                      (                                          k                      -                      1                                        )                                                  ⁡                                  (                  i                  )                                            )                                =                                    (                                                z                                      N                    -                    k                    +                    1                                                  -                                                      ∑                                          p                      =                      1                                                              k                      -                      1                                                        ⁢                                                            r                                                                        N                          -                          k                          +                          1                                                ,                                                  N                          -                          p                          +                          1                                                                                      ⁢                                          c                                                                        N                          -                          p                          +                          1                                                ,                                                                              Π                            p                                                          (                                                              k                                -                                1                                                            )                                                                                ⁡                                                      (                            i                            )                                                                                                                                                          )                        /                          r                                                N                  -                  k                  +                  1                                ,                                  N                  -                  k                  +                  1                                                                    ,                                  ⁢                                  ⁢                  i          =          1                ,        2        ,        …        ⁢                                  ,                  S                      k            -            1                                              (        22        )                                                          ⁢                              u                                          N                -                k                +                1                            ,              i                                ⁡                      (                                          Π                                  (                                      k                    -                    1                                    )                                            ⁡                              (                i                )                                      )                                              (        23        )            
In the ASESS method, a surviving path on the k-th stage is adaptively selected as following. In the ASESS method, a representative cumulative metric value E(i) and a current rank ρ(i) of each surviving path which is survived on the k−1-th stage are first initialized so as to obtain expression (24), expression (25), and expression (26).E(i):=dk−1(Π(k−1)(i))  (24)ρ(i):=1  (25)q:=1  (26)
In the ASESS method, a candidate replica on the ρ(imin)-th order in the ranking of imin at which ρ(i)≦mN−k+1 is satisfied and E(i) has the minimum value is selected from the symbol ranking table and the q-th surviving path on the k-th stage is expressed as expression (27) and expression (28).
                                                        Π                                                1                  ~                  k                                -                1                                            (                k                )                                      ⁡                          (              q              )                                =                                    Π                              (                                  k                  -                  1                                )                                      ⁡                          (                              i                                  m                  ⁢                                                                          ⁢                  i                  ⁢                                                                          ⁢                  n                                            )                                      ⁢                                  ⁢                                            Π              k                              (                k                )                                      ⁡                          (              q              )                                =                                    Ω                              (                                  m                                      N                    -                    k                    +                    1                                                  )                                      ⁡                          (                                                                    ɛ                                          (                      k                      )                                                        ⁡                                      (                                          i                                              m                        ⁢                                                                                                  ⁢                        i                        ⁢                                                                                                  ⁢                        n                                                              )                                                  ,                                  ρ                  ⁡                                      (                                          i                                              m                        ⁢                                                                                                  ⁢                        i                        ⁢                                                                                                  ⁢                        n                                                              )                                                              )                                                          (        27        )                                          i                      m            ⁢                                                  ⁢            i            ⁢                                                  ⁢            n                          =                              arg                                          ρ                ⁡                                  (                  i                  )                                            ≤                              m                                  N                  -                  k                  +                  1                                                              ⁡                      (                          min              ⁡                              [                                  E                  ⁡                                      (                    i                    )                                                  ]                                      )                                              (        28        )            
A cumulative metric is calculated as expression (29).
                                          d            k                    ⁡                      (                                          Π                                  (                  k                  )                                            ⁡                              (                q                )                                      )                          =                                            d                              k                -                1                                      ⁡                          (                                                Π                                      (                                          k                      -                      1                                        )                                                  ⁡                                  (                                      i                                          m                      ⁢                                                                                          ⁢                      i                      ⁢                                                                                          ⁢                      n                                                        )                                            )                                +                                                                                    z                                      N                    -                    k                    +                    1                                                  -                                                      ∑                                          p                      =                      1                                                              k                      -                      1                                                        ⁢                                                            r                                                                        N                          -                          k                          +                          1                                                ,                                                  N                          -                          p                          +                          1                                                                                      ⁢                                          c                                                                        N                          -                          p                          +                          1                                                ,                                                                              Π                            p                                                          (                              k                              )                                                                                ⁡                                                      (                            q                            )                                                                                                                                              -                                                      r                                                                  N                        -                        k                        +                        1                                            ,                                              N                        -                        k                        +                        1                                                                              ⁢                                      c                                                                  N                        -                        k                        +                        1                                            ,                                                                        Π                          k                                                      (                            k                            )                                                                          ⁡                                                  (                          q                          )                                                                                                                                                        2                                              (        29        )            
Then, in the ASESS method, the cumulative metric is updated as expression (30), expression (31), and expression (32), and the above-mentioned processing is performed until q reaches the number Sk of surviving paths of the k-th stage.E(imin):=dk(Π(k)(q))  (30)ρ(imin):=ρ(imin)+1  (31)q:=q+1  (32)
The followings are examples of related art.
K. J. Kim and J. Yue, “Joint channel estimation and data detection algorithms for MIMO-OFDM systems,” in Proc. Thirty-Sixth Asilomar Conference on Signals, Systems and Computers, pp. 1857-1861, November 2002
K. Higuchi, H. Kawai, N. Maeda and M. Sawahashi, “Adaptive Selection of Surviving Symbol Replica Candidates Based on Maximum Reliability in QRM-MLD for OFCDM MIMO Multiplexing,” Proc. of IEEE Globecom 2004, pp. 2480-2486, November 2004
K. Higuchi, H. Kawai, N. Maeda and M. Sawahashi, “Adaptive Selection Algorithm of Surviving Symbol Replica Candidates in QRM-MLD for MIMO Multiplexing Using OFCDM Wireless Access”, RCS2004-69, May 2004